/* 
 * File:   main.cpp
 * Author: trunghpb
 *
 * INPUT:
 * N U V lần lượt là số đỉnh, đỉnh đầu, đỉnh cuối.
 * N dòng tiếp mỗi dòng một dãy i số, số thứ j của dòng thứ i thể hiện độ dài đường đi ij.
 *
 * OUTPUT:
 * L dòng đầu là độ dài bé nhất tìm được
 * dòng sau ghi các đỉnh lần lượt phải qua để đi từ U->V (bao gồm cả U,V)
 * Created on March 23, 2010, 11:40 PM
 */

#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAXINT (int)(pow(2,16) - 1)

#define MAX 100
#define TRUE 1
#define FALSE 0

int a[MAX][MAX];
int N, U, V;
int last[MAX], chuaxet[MAX];
long d[MAX];

void input(){
    FILE *fi;
    fi = fopen("data.in", "r");
    fscanf(fi, "%d %d %d\n", &N, &U, &V);
    int tmp;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            fscanf(fi, "%d", &tmp );
            a[i][j] = tmp == 0? MAXINT : tmp;
        }
        fscanf(fi, "\n");
    }
    fclose(fi);
}
void init(){
    U--; V--;
    for(int i=0; i<N; i++){
        d[i] = a[U][i];
        last[i] = U;
        chuaxet[i] = TRUE;
    }
    last[U] = -1;
    chuaxet[U] = FALSE;
    d[U] = 0;
}
void dijktra(){
    long mind;
    int s;
    for(int i=0; i<N-1; i++){
        if (i != U){
            mind = MAXINT;
            for(int j = 0; j < N; j++){
                if (chuaxet[j]){
                    if (d[j] < mind){
                        mind = d[j];
                        s = j;
                    }
                }
            }
            chuaxet[s] = FALSE;
            for (int j = 0; j<N; j++){
                if (chuaxet[j]){
                    if (d[j] > mind + a[s][j]){
                        d[j] = mind + a[s][j];
                        last[j] = s;
                    }
                }
            }
        }
    }
}
void output(){
    FILE *fo;
    fo = fopen("dijkstra.out", "w");
    int dd[MAX], len = 0;
    int t = V;
    while (t != -1){
        dd[len++] = t;
        t = last[t];
    }
    fprintf(fo, "%d\n", d[V]);
    for(int i=len-1; i>=0; i--){
        fprintf(fo, "%d ", dd[i] + 1);
    }
    
    fclose(fo);
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();
    init();
    dijktra();
    output();
    return (EXIT_SUCCESS);
}

